package treesNgraphs;

/**
 * Created by Tzachi on 11/10/2014.
 * <p/>
 * Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined
 * to be a tree such that no two leaf nodes differ in distance from the root by more than one.
 * <p/>
 * Solution:
 * The difference of min depth and max depth should not exceed 1.
 */

public class BalancedTreeChecker {

    public static int maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(node.getLeftChild()), maxDepth(node.getRightChild()));
    }

    public static int minDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.min(minDepth(node.getLeftChild()), minDepth(node.getRightChild()));
    }

    public static boolean isBalanced(TreeNode root) {
         return (maxDepth(root) - minDepth(root) <= 1);
    }


}